package cn.corffen.test.algorithm.practice;

import java.util.Arrays;

public class Sort {


    public static void main(String[] args) {

        Sort demo = new Sort();
        int[] array = {4, 3, 3, 4, 2, 6, 1};
        demo.quickSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 最好复杂度是O(n)
     * 最差是O(n²)
     *
     * @param arr
     */
    private void bubbleSort(int[] arr) {
        boolean swap = false;
        int temp = 0;
        for (int i = arr.length - 1; i > 0; i--) {
            swap = false;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swap = true;
                }
            }
            if (!swap) {
                break;
            }
        }
    }

    private void mergeSort(int[] arr) {
        int[] aux = new int[arr.length];
        mergeSortHelper(arr, aux, 0, arr.length - 1);
    }

    private void mergeSortHelper(int[] a, int[] aux, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSortHelper(a, aux, lo, mid);
        mergeSortHelper(a, aux, mid + 1, hi);
    }

    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        for (int i = lo; i < hi; i++) {
            aux[i] = a[i];
        }
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k < hi; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
            } else if (a[i] > a[j]) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

    /**
     * 最坏情况下,时间复杂度 是O(n²)
     * 平均复杂度是O(nlogn)
     * 最好复杂度是O(nlogn)
     * <p>
     * 一般情况是比归并排序要快一些
     *
     * @param arr
     */
    private void quickSort(int[] arr) {
        quickHelper(arr, 0, arr.length - 1);
    }

    private void quickHelper(int[] arr, int lo, int hi) {
        //递归要有结束条件
        if (lo >= hi) {
            return;
        }
        int partition = partition(arr, lo, hi);
        quickHelper(arr, lo, partition - 1);
        quickHelper(arr, partition + 1, hi);
    }

    private int partition(int[] arr, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int pivot = arr[lo];//比较的基点
        while (true) {
            while (arr[++i] < pivot) {
                if (i == hi) {
                    break;
                }
            }
            while (arr[--j] > pivot) {
                if (j == lo) {
                    break;
                }
            }
            //左指针大于等于右指针就停下来
            if (i >= j) {
                break;
            }
            //否则就交换这两个指针
            swap(arr, i, j);
        }
        swap(arr, lo, j);
        return j;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
